package com.xhj.joffer.stack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * -
 *
 * @author 见见 pure_xhj@163.com @Date 2021-09-05 @Time 9:54
 */
public class StackPutOrderCheckPopOrder {
  public static void main(String[] args) {
    int[] pushed = {1, 2, 3, 4, 5};
    int[] popped = {4, 5, 3, 2, 1};
    boolean result = test01(pushed, popped);
    System.out.println("result = " + result);
    System.out.println("==================================================");
    int[] pu = {1, 2, 3, 4, 5};
    int[] po = {4, 3, 5, 1, 2};
    boolean re = test01(pu, po);
    System.out.println("re = " + re);
    System.out.println("==================================================");
    int[] u = {2, 1, 0};
    int[] o = {1, 2, 0};
    boolean r = test01(u, o);
    System.out.println("r = " + r);
  }
  /** 思路一: 遍历压入顺序, 用弹出顺序做校验 */
  @Test
  public static boolean test01(int[] pushed, int[] popped) {
    System.out.println("=============test01==============");
    System.out.println("思路一: 遍历压入顺序, 用弹出顺序做校验");
    long time01 = System.currentTimeMillis();

    System.out.println("pushed = " + Arrays.toString(pushed));
    System.out.println("popped = " + Arrays.toString(popped));

    boolean result = false; // - - - - - - -全部校验完成, 变为true, 程序终止
    // 遍历
    boolean innerMakePopBreak = false;
    int popNow = 0, pushNow = 0; // - - - - - - -标记当前位置
    List have = new ArrayList<Integer>();
    // 遍历弹出顺序
    for (int op = popNow; op < popped.length; op++) {
      popNow = op; // - - - - - - -刷新popNow
      // 遍历栈内剩余元素, 看当前栈尾是否是弹出元素
      if (have.size() == 0) {
        if (pushNow == pushed.length) {
          break; // - - - - - - -没有可用元素了, 直接return false
        }
        have.add(pushed[pushNow++]); // - - - - - - -当前剩余为空, push
      }
      // 遍历, 弹出栈尾
      for (int h = have.size() - 1; h >= 0; h--) {
        if (have.get(h).equals(popped[popNow])) {
          have.remove(h); // - - - - - - -当前弹出元素恰巧是当前栈尾元素, 弹出, 执行havefor, 看是否继续弹出
          if (popNow == popped.length - 1) {
            result = true;
            innerMakePopBreak = true; // - - - - - - -最后一个也已经弹出, 万事大吉, over
          }
          popNow++; // - - - - - - -刷新弹出索引
          h = have.size(); // - - - - - - -刷新栈尾索引
          // 若h==0, add, 以便继续执行havefor
          if (h == 0) {
            if (pushNow == pushed.length) {
              innerMakePopBreak = true;
              break; // - - - - - - -没有可用元素了, 直接return false
            }
            have.add(pushed[pushNow++]); // - - - - - - -压入一个元素, 执行栈尾弹出
            h = have.size(); // - - - - - - -刷新栈尾索引
          }
        } else {
          if (pushNow == pushed.length) {
            innerMakePopBreak = true;
            break; // - - - - - - -没有可用元素了, 直接return false
          }
          have.add(pushed[pushNow++]); // - - - - - - -压入一个元素, 执行栈尾弹出
          h = have.size(); // - - - - - - -刷新栈尾索引
        }
      }
      if (innerMakePopBreak == true) {
        break;
      }
    }
    // 边界情况
    if (pushed.length != popped.length) {
      System.out.println("输入参数不合法");
    } else {
      if (popped.length == 0) {
        result = true;
      }
    }

    long time0101 = System.currentTimeMillis() - time01;
    System.out.println("\n耗时 =  " + time0101 + "ms");
    System.out.println("=================================");

    return result;
  }
}
